package 集合;

import java.util.*;

public class No451根据字符出现频率排序 {

    public static String frequencySort(String s) {
        char arr[] = s.toCharArray();
        Map<Character,Integer> map=new HashMap<>();
        for(int i=0;i<arr.length;i++){
            map.put(arr[i],map.getOrDefault(arr[i],0)+1);
        }
        Map<Integer, List<Character>> map2=new HashMap<>();
        List<Integer> sortList=new ArrayList<>();
        for(char c : map.keySet()){
            Integer op = map.get(c);//获取次数
            if(map2.get(op)==null){
                sortList.add(op);
                List<Character> list=new ArrayList<>();
                list.add(c);
                map2.put(op,list);
            }else{
                List<Character> list = map2.get(op);
                list.add(c);
            }
        }

        Collections.sort(sortList);

        StringBuilder str=new StringBuilder();

        for(int i=sortList.size()-1;i>=0;i--){
            int count=sortList.get(i);
            List<Character> list = map2.get(count);
            list.forEach(l->{
                for(int j = 0; j< count; j++){
                    str.append(l);
                }
            });
        }
        return str.toString();
    }

    public static String frequencySortHeap(String s) {

        int[] arr=new int[128];

        for(int i=0;i<s.length();i++){
            char c=s.charAt(i);
            arr[c]++;
        }

        PriorityQueue<Character> priorityQueue=
                new PriorityQueue<Character>(128, new Comparator<Character>() {
                    @Override
                    public int compare(Character o1, Character o2) {
                        return -(arr[o1]-arr[o2]);
                    }
                });

        for(int i=0;i<arr.length;i++){
            if(arr[i]!=0)
                priorityQueue.add((char) i);
        }

        StringBuilder stringBuilder=new StringBuilder();
        while(!priorityQueue.isEmpty()){
            Character character = priorityQueue.poll();
            while(arr[character]!=0){
                stringBuilder.append(character);
                arr[character]--;
            }
        }

        return stringBuilder.toString();

    }

    public static void main(String[] args) {
        String str = frequencySortHeap("tree");
        System.out.println(str);
    }


}
